#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution
{
public:
    bool isInterleave(string s1, string s2, string s3)
    {
        if (s1.size() + s2.size() != s3.size())
            return false;
        vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, -1));
        dp[s1.size()][s2.size()] = 1;
        return CanInterleave(s1, s2, s3, dp, 0, 0);
    }

    bool CanInterleave(const string &s1, const string &s2, const string &s3, vector<vector<int>> &dp, int i1, int i2)
    {
        if (dp[i1][i2] != -1)
            return dp[i1][i2] == 1;
        if (i1 == s1.size())
            dp[i1][i2] = (s2[i2] == s3[i1 + i2] && CanInterleave(s1, s2, s3, dp, i1, i2 + 1)) ? 1 : 0;
        else if (i2 == s2.size())
            dp[i1][i2] = (s1[i1] == s3[i1 + i2] && CanInterleave(s1, s2, s3, dp, i1 + 1, i2)) ? 1 : 0;
        else
            dp[i1][i2] = (s2[i2] == s3[i1 + i2] && CanInterleave(s1, s2, s3, dp, i1, i2 + 1) ||
                          s1[i1] == s3[i1 + i2] && CanInterleave(s1, s2, s3, dp, i1 + 1, i2))
                             ? 1
                             : 0;
        return dp[i1][i2] == 1;
    }
};
int main()
{
    cout << "Code97" << endl;
    Solution s;
    string s1 = "aasb";
    string s2 = "db";
    string s3 = "aadbb";
    cout << boolalpha << s.isInterleave(s1, s2, s3) << endl;
    return 0;
}